class Solution {
    Map<Integer, Double> cache = new HashMap<>();
    public double myPow(double x, int n) {
        if (cache.get(n) == null) {
            double ans = 1d;
            if (n < 0) {
                ans = 1 / (x * myPow(x, -(n + 1)));
            } else if (n == 0) {
                ans = 1;
            } else if (n % 2 == 0) {
                ans = myPow(x, n/2) * myPow(x, n/2);
            } else {
                ans = myPow(x, n/2) * myPow(x, n/2) * x;
            }
            cache.put(n, ans);
            return ans;
        }
        return cache.get(n);
    }
}
